package main

import (
	"fmt"
)

/*
	判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
 */

func isSubsequence(s string, t string) bool {
	// 思路1 求最长公共子序列 判断长度是否与s 相同
	maxN := func(x, y int) int  {
		if x > y {
			return x
		}
		return y
	}
	dp := make([][]int, len(s) + 1)
	for i := 0; i <= len(s); i ++ {
		dp[i] = make([]int, len(t) + 1)
	}
	// fmt.Println(dp)
	for i := 1; i <= len(s); i ++ {
		for j := 1; j <= len(t); j ++ {
			if s[i - 1] == t[j - 1] {
				dp[i][j] = dp[i - 1][j - 1] + 1
			}else {
				dp[i][j] = maxN(dp[i - 1][j], dp[i][j - 1])
			}
		}
	}
	// fmt.Println(dp[len(s)][len(t)])
	return dp[len(s)][len(t)] == len(s)
}

// 思路2 遍历t 并让s从底部出栈
func isSubsequence2(s string, t string) bool {
	for i := range t {
		if len(s) > 0 && t[i] == s[0]   {
			s = s[1:]
		}

	}
	return len(s) == 0
}


func main() {
	fmt.Println(isSubsequence2("ace", "affce"))
}
